1. Field of the Invention
This invention relates generally to the area of error detection for digital computer systems and more specifically to parity prediction logic for high-speed binary adders.
2. DESCRIPTION OF THE PRIOR ART
A binary adder is a vital component of electronic digital computer systems. The speed and reliability of the binary adder are, therefore, major concerns in computer system design. It is well known that a carry-look-ahead adder generates the result of an operation on two operands faster than a ripple carry adder. It is also known that a carry-look-ahead adder can be implemented in many different ways. This invention is not concerned with design of a high-speed binary adder, but rather relates to the design of checking logic for error detection in a high speed adder.
In the past, computers were used largely in an off-time, batch-processing mode and the consequences of undetected hardware malfunctions were relatively minor. Today, digital computers, even main-frame computers, are utilized in on-line information processing, data entry and retrieval, and real-time control of processes. Incorrect computer operation in any of these applications must be detected as soon as possible. At the same time, the increased size and complexity of digital computers have made it more and more difficult to ensure correct machine operation.
In modern computer systems, operational reliability is supported by built-in error detection. A commonly used method of error detection is parity checking. Conventionally, in a parity checking procedure, a "parity" bit is generated in response to the number of "ones" in an arbitrary group of bits. Typically, for a byte, comprising eight bits of data, the parity bit will take on a digital value (1 or 0) which will make the sum of ones in the combined group of nine bits odd, if odd parity applies, or even, if even parity.
In modern computer architecture, data is transferred or exchanged between architectural units in a standard format. For example, data is transferred in the form of sequences in multi-byte "words" in many contemporary architectures. It is the case that a parity bit accompanies each byte being transferred to that transfer of a four-byte word involves thirty-six bits.
When words are operated upon by computer elements, as, for example, in an adder, the parity bits are separated and separately treated. When two words are combined in an adder to produce a result word, parity bits must be generated for each byte of the result. Formerly, parity bits for the result word were generated when the word was available from the adder. In this case, the parity bits were generated by operating on the result. It is now standard practice to increase the speed of conventional adder operations by "predicting" parity bits for the results in a parity predict operation performed concurrently with the add operation. In such schemes, predicted parity is generated and then compared to the actual parity of the result word. If disparity is detected, an error signal generated by the comparison causes the adder to repeat its operation. If a second error is detected, it is assumed that the adder has malfunctioned.
The operation of an adder generally involves two multi-bit operands. In combining the operands to produce a result, the operand bits are transformed as well as transferred by the binary adder and the resultant parity bits of the result are difficult to predict. To solve this particular problem, a commonly used technique for adder error checking is to employ two identical adders in the system and to compare their results bit-by-bit to check that the operation is error free. Another technique is to have three identical adders in the system and "take a majority vote" among the three results to identify an adder that has erred.
Each of the above-mentioned techniques has disadvantages. First, it is expensive to duplicate (and even more so to triplicate) the same adder logic. Second, a parity bit cannot be preserved throughout the operation of the adder system. This is undesirable when all other areas of the same system have parity bits carried throughout.
A preferred approach is to construct parity predicting logic to predict the correct parity for the output of the adder. The predicted parity could then be compared to the actual parity of the sum. If unequal, an error signal is generated which causes the adder to repeat the addition. If another error is detected, it is assumed that the adder has failed.
Parity prediction schemes are shown in Louie, U.S. Pat. No. 3,925,647 and Kalandra et al, IBM TDB Vol. 23, No. 12 (5/81). These schemes include parity prediction circuits which are very complex and may cause more delay than the adder itself. Elimination of delay is important, particularly in pipelined processing systems. The parity prediction delays cause the system designer to be faced with a trade-off: allow the system to operate at the speed of the adder and provide for means to unravel the system errors caused by errors in the adder, or slow the system to allow for the delays of the parity prediction circuit.
Another parity prediction scheme is shown in Taylor, U.S. Pat. No. 3,911,261. However, the scheme of Taylor only provides a "best guess" predicted parity. The increased error and delays caused by inaccurate "guesses" are unacceptable in modern computing systems.